package Classic150;

import Tree.TreeNode;

import java.util.Stack;

public class 二叉搜索树中第K小的元素 {

    int k;
    int res;

    public int kthSmallest(TreeNode root, int k) {
        /*
            深度优先搜索-迭代，中序
         */
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                if (--k == 0) return root.val;
                root = root.right;
            }
        }
        return -1;

        /*
            深度优先搜索-递归，中序
         */
        /*this.k = k;
        inorder(root);
        return res;*/
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if(--k == 0) res = root.val;
        inorder(root.right);
    }
}
